package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/surrounded-regions'>被围绕的区域(Surrounded Regions)</a>
 * <p>给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
 * <ul>
 *     <li>连接：一个单元格与水平或垂直方向上相邻的单元格连接。</li>
 *     <li>区域：连接所有 'O' 的单元格来形成一个区域。</li>
 *     <li>围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。</li>
 * </ul>
 * </p>
 * <p>通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 *              X   X   X   X               X   X   X   X
 *              X   O   O   X       ==>     X   X   X   X
 *              X   X   O   X               X   X   X   X
 *              X   O   X   X               X   O   X   X
 *
 *      输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 *      解释：
 *          在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
 *
 *  示例 2：
 *      输入：board = [["X"]]
 *      输出：[["X"]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>m == board.length</li>
 *     <li>n == board[i].length</li>
 *     <li>1 <= m, n <= 200</li>
 *     <li>board[i][j] 为 'X' 或 'O'</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/7 16:19
 */
public class LC0130SurroundedRegions_M {
    static class Solution {
        public void solve(char[][] board) {
            // 可以是非'X' 非'O'的任意字符
            char flag = 'Q';
            int m = board.length;
            int n = board[0].length;
            // 从边缘的'O'向内搜索，如果遇到'O',先修改为flag。
            for (int row = 0; row < m; row++) {
                dfs(board, row, 0, m, n, flag);     // 每一行的第一列
                dfs(board, row, n - 1, m, n, flag); // 每一行的最后一列
            }
            for (int i = 0; i < n; i++) {
                dfs(board, 0, i, m, n, flag);       // 第一行的每一列
                dfs(board, m - 1, i, m, n, flag);   // 最后一行的每一列
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 将标记的恢复成'O',未被标记的替换为'X'
                    if (board[i][j] == flag) {
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                }
            }
        }

        private void dfs(char[][] board, int row, int col, int m, int n, char flag) {
            // 越界 与 非'O'字符，不作处理
            if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
                return;
            }
            board[row][col] = flag;
            dfs(board, row - 1, col, m, n, flag);
            dfs(board, row + 1, col, m, n, flag);
            dfs(board, row, col - 1, m, n, flag);
            dfs(board, row, col + 1, m, n, flag);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solve(new char[][]{{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}});
    }

}
